package org.tonny.algorithm.leetcode;

import java.util.*;

/**
 * 210. 课程表 II
 */
public class LeetCode210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> result = new ArrayList<>();
        //记录入度
        int[] indegrees = new int[numCourses];
        //用于存储课程之间的先后关系
        Map<Integer, ArrayList<Integer>> preMap = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            preMap.put(i, new ArrayList<>());
        }
        for (int[] prerequisit : prerequisites) {
            int pre = prerequisit[1];
            int post = prerequisit[0];
            preMap.get(pre).add(post);
            //记录入度
            indegrees[post]++;
        }

        //将入度为0的值加入到队列中，用于遍历
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }

        // 广度遍历
        while (!queue.isEmpty()) {
            Integer current = queue.poll();
            result.add(current);
            for (Integer pos : preMap.get(current)) {
                indegrees[pos]--;
                if (indegrees[pos] == 0) {
                    queue.add(pos);
                }
            }
        }
        if (result.size() != numCourses) {
            return new int[]{};
        }

        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = result.get(i);
        }
        return res;
    }
}